/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.search;

import java.util.PriorityQueue;

import kaist.sep502.tsp.algorithm.heuristic.Heuristic;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.model.Solution;

/**
 * @author minho kim
 * 
 */
public class IterativeDeepeningSearch extends SearchAlgorithm {
	private double compNumber = 0.1;
	/**
	 * @param problem
	 */
	public IterativeDeepeningSearch(Problem problem) {
		super(problem);
	}


	private PriorityQueue<CityPath> frontier;
	private PriorityQueue<CityPath> goalCityPathList = new PriorityQueue<CityPath>();
	private int limitStep = 0;

	/*
	 * (non-Javadoc)
	 * 
	 * @see kaist.sep502.tsp.algorithm.search.SearchAlgorithm#search()
	 */
	@Override
	public Solution search() {
		Solution solution = new Solution("Iterative Deepening");
		solution.expandedNodeCount = 0;
		solution.startStopWatch();

		// AStar 값 출력.
		double limitCost = new AStarSearch(this.problem).search().goalCityPath.getPathCost()+compNumber;
		Heuristic heuristic;

		frontier = new PriorityQueue<CityPath>(2000000);
		CityPath cityPath = new CityPath(problem, problem.departureCityNo);
		frontier.add(cityPath);
		int citySize = problem.citySize;
		
		for (; limitCost > 0.0; limitCost -= 0.1, limitStep++) {
			
			try{
				while (frontier.isEmpty() != true) {
					solution.expandedNodeCount++;
					cityPath = frontier.poll();
					int tempCityNo;
					for (int i = 0; i < citySize; i++) { // i는 cityNo가 아님.
						tempCityNo = problem.cityList.get(i).getCityNo();
						// 이미 들린 도시이면 제외
						if (visited(cityPath, tempCityNo)) 	continue;
						
						// 도시 경로 정보를 만든다.
						CityPath newCityPath = cityPath.clone();
						
						heuristic = heuristicAlgorithm.getHx(problem, newCityPath, tempCityNo);
						newCityPath.moveTo(problem, heuristic.cityNo, heuristic.hx);
						
						
						// Goal에 맞는지 확인.
						if (problem.checkGoal(newCityPath)) {
							goalCityPathList.add(newCityPath);
						} else if ((double) newCityPath.getPathCost() <= (double)limitCost) {
							frontier.add(newCityPath);
						}
					}
				}
				
			} catch (Exception e){
				e.printStackTrace();
			}
		}

		
		if(goalCityPathList.isEmpty() != true){
			solution.setGoalCityPath(goalCityPathList.poll());
			solution.stopStopWatch();
			solution.setSuccess(true);
		}
		
		return solution;
	}

	// TODO 문제 있을 아래 로직을 체크해볼 것 
	private boolean visited(CityPath cityPath, int cityNo) {
		if (cityPath.tourHistory.size() == problem.citySize && cityNo == problem.goalCityNo) {
			return false;
		}
		
		return cityPath.tourHistory.contains(cityNo);
	}

	/**
	 * @return the compNumber
	 */
	public double getCompNumber() {
		return compNumber;
	}

	/**
	 * @param compNumber the compNumber to set
	 */
	public void setCompNumber(double compNumber) {
		this.compNumber = compNumber;
	}

}
